public class HashBuck {
    //哈希桶的实现
    static class Node{
        public int key;
        public int val;
        public Node next;
        public Node(int key,int val){
            this.key=key;
            this.val=val;
        }
    }
    public Node[] array;
    public int usedSize;
    //进行设置负载因子；
    public double local_factor=0.75;
    public HashBuck(){
        array=new Node[10];
    }
    //进行向哈希桶中放入元素；
    public void put(int key,int val){
        int index=key% array.length;//进行位置查找；
        Node cur=array[index];//找到位置对应的链表；
        //进行遍历链表；
        while(cur!=null){
            if(cur.key==key){
                cur.val=val;
                return;
            }
            cur=cur.next;
        }
        //指向到这里：说明就没有重复的key值进行更改了；
        //下面我们进行向链表中放入这个新的节点；
        //此处采用头插法进行插入；
        Node newNode=new Node(key, val);
        newNode.next=array[index];
        array[index]=newNode;
        this.usedSize++;
        //每次进行放入一个节点后，我们要进行考虑一下，是否超出负载因子的限定；
        if(doFactor()>=local_factor){
            //进行扩容操作；
            grow();
        }
    }
    public double doFactor(){
        return usedSize*1.0/ array.length;
    }
    public void grow(){
       Node[] newArray=new Node[2* array.length];
       //需要将哈希桶中的数据放入到新的桶中；
        //这就需要我们进行遍历原哈希桶；
        for(int i=0;i< array.length;i++){
            //每一个数组元素都是属于一个链表；
            //并且每个链表都一一进行遍历当中的节点；
            //进行确定当前key在新的哈希桶中的位置；
            Node cur=array[i];
            while(cur!=null){
                int newIndex=cur.key%newArray.length;//进行确定新哈希桶的位置；
                Node curNext=cur.next;//进行记录原哈希桶的下一个节点位置；
                //进行将原哈希桶中的元素采用头插法插入到新的哈希桶中；
                cur.next=newArray[newIndex];
                newArray[newIndex]=cur;
                cur=curNext;//进行开始原哈希桶的当前链表的下一个节点；
            }
        }
        this.array=newArray;//指向新的引用；
    }
    //进行获取哈希桶中的值；
    public int get(int key){
        int index=key% array.length;
        Node cur=array[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.val;
            }
            cur=cur.next;
        }
        return -1;
    }


}
